package hot100.logos1To10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author logos
 * date 2025/7/9 19:44
 * @version v1.0
 * @Package hot100
 */
public class logos6 {


    /**
     * 6.三数之和
     * https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            int n = nums.length;
            for (int i = 0; i < n - 2; i++) {
                if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                    break;
                }
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                if (nums[i] + nums[n - 2] + nums[n - 1] < 0) {
                    continue;
                }
                int j = i + 1;
                int k = n - 1;
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum > 0) {
                        k--;
                    } else if (sum < 0) {
                        j++;
                    } else {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                        while (j < k && nums[j] == nums[++j]);
                        while (j < k && nums[k] == nums[--k]);
                    }
                }
            }
            return ans;
        }
    }
}
